package Offer.offer;

import domain.ListNode;

/**
 * 合并两个排序的链表
 *
 * @author leiwenkang
 * @date 2020/4/6
 */
public class Test17合并两个排序的链表 {
    public static void main(String[] args) {
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(3);
        ListNode p3 = new ListNode(5);
        ListNode p4 = new ListNode(7);
        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = null;
        ListNode p5 = new ListNode(2);
        ListNode p6 = new ListNode(4);
        ListNode p7 = new ListNode(6);
        ListNode p8 = new ListNode(8);
        p5.next = p6;
        p6.next = p7;
        p7.next = p8;
        p8.next = null;
        ListNode p = merge(p1, p5);
        while (p != null) {
            System.out.print(p.val);
            System.out.print(" ");
            p = p.next;
        }
    }
    //递归
    public static ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }

        if (head2 == null) {
            return head1;
        }

        ListNode head;
        if (head1.val <= head2.val) {
            head = head1;
            head.next = merge(head1.next, head2);
        } else {
            head = head2;
            head.next = merge(head1, head2.next);
        }
        return head;
    }

    //非递归
    public static ListNode mergeListNode(ListNode head1, ListNode head2) {
        ListNode p1 = head1;
        ListNode p2 = head2;

        ListNode head = new ListNode(-1);
        ListNode p = head;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }

        while (p1 != null) {
            p.next = p1;
            p1 = p1.next;
            p = p.next;
        }

        while (p2 != null) {
            p.next = p2;
            p2 = p2.next;
            p = p.next;
        }

        return head.next;
    }
}
